package  main.java.leetcode.editor.cn;
//2023-07-03 16:05:34
//节点间通路。给定有向图，设计一个算法，找出两个节点之间是否存在一条路径。 
//
// 示例1: 
//
//  输入：n = 3, graph = [[0, 1], [0, 2], [1, 2], [1, 2]], start = 0, target = 2
// 输出：true
// 
//
// 示例2: 
//
//  输入：n = 5, graph = [[0, 1], [0, 2], [0, 4], [0, 4], [0, 1], [1, 3], [1, 4], [
//1, 3], [2, 3], [3, 4]], start = 0, target = 4
// 输出 true
// 
//
// 提示： 
//
// 
// 节点数量n在[0, 1e5]范围内。 
// 节点编号大于等于 0 小于 n。 
// 图中可能存在自环和平行边。 
// 
// Related Topics 深度优先搜索 广度优先搜索 图 👍 82 👎 0

import java.util.*;

class RouteBetweenNodesLcci {
    public static void main(String[] args) {
        //创建该题目的对象方便调用
        Solution solution = new RouteBetweenNodesLcci().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    /***
    * @author LazyCat
    * @date  2023/7/3
    * @param
    * @return
     * 使用map先进行构建图,然后进行bfs或者dfs进行遍历图,如果遍历值能与target相等则说明可以到达
     * 返回true，否则返回false
    */
    public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {

        Map<Integer, List<Integer>> graphMap = new HashMap<>();

        for(int[] arr : graph){
            if(!graphMap.containsKey(arr[0])){
                graphMap.put(arr[0],new ArrayList<>());
            }
            graphMap.get(arr[0]).add(arr[1]);
        }

        return bfs(graphMap,start,target,n);
    }

    private boolean bfs(Map<Integer,List<Integer>> map,int start,int target,int n){

        LinkedList<Integer> queue = new LinkedList<>();
        queue.add(start);
        boolean[] visited = new boolean[n];
        visited[start] = true;
        while (!queue.isEmpty()){
            int temp = queue.pop();
            List<Integer> list = map.get(temp);
            if(list == null){
                continue;
            }

            for (int val : list){
                if(val == target){
                    return true;
                }

                if(visited[val] == true){
                    continue;
                }

                visited[val] = true;
                queue.add(val);
            }
        }
        return false;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
